package com.sx.sx1.lintcode.day717;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

// LC 345 · 数组求和 vip simple 前缀和
public class LC345 {

    static class Solution {
        /**
         * @param arr: An array
         * @return: An array
         */
        public int[] getSum(int[] arr) {
            //前缀和
            int n = arr.length;
            Map<Integer,Integer> pos = new HashMap<>();
            for (int i = 0; i < n; i++) {
                pos.put(arr[i],i);
            }

            int[] ans = new int[n];
            Arrays.sort(arr);
            int sum =0;
            for (int i = 0; i <n ; i++) {
                int cur = arr[i];
                sum+=arr[i];
                ans[pos.get(cur)] = sum-arr[i];
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        int[] arr = {2,4,8,3};
        Solution obj = new Solution();
        int[] data = obj.getSum(arr);
        for (int datum : data) {
            System.out.print(datum+" ");
        }
    }



}


/*
\LintCode-Logo
学习
刷题
题集
群组

内推
VIP
CAT
其他...
搜索题目、标签、题集
邀请有礼
中文
avatar
您有411条未读消息，请及时查看
345 · 数组求和
算法
简单
通过率
48%
题目
题解7
笔记
讨论2
排名
记录
描述
因为小千数学加法考试不及格，作为惩罚，她的哥哥给她出了一道数学加法题。
给定一个数组A，找到数组A中所有小于当前位置A[i]的数字，并求出所有小于A[i]的数字之和，保存在B[i]的位置上。小千还是不会这个题目，聪明的你能帮帮小千得到这个新的数组吗？

仅限7天：《微博评论系统项目实战》早鸟价￥199

微信加【jiuzhang1104】备注【微博】了解详情&参与拼团


1<=n<=50000
数组 A 中没有重复元素
样例
样例 1：

输入：
[2,4,8,3]
输出：
[0,5,9,2]
解释：
没有小于2的数字；
小于4的有[2,3]，和为5；
小于8的有[2,4,3]，和为9；
小于3的有[2]
标签
推荐课程

0基础入门数据分析
进阶大厂刚需高薪人才，熟练掌握SQL、Python、Tableau、A/Btest等实用技能工具，配套100+数据题夯实基础
81/2225
已开启智能提示
发起考试
15 分 00 秒
123456789
public class Solution {
    /**
     * @param arr: An array
     * @return: An array
     */
/*
public int[] getSum(int[] arr) {
        // Write your code here.
        }
        }
        控制台
        历史提交

        */

